package BinaryTreePackage2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class Traversal_ {
  List<Integer> result = new ArrayList<>();


  public List<Integer> postorderTraversal(TreeNode root) {
    postorderTraversalBackTracking(root);
    return result;
  }

  // 1. 确定参数和返回值
  public void postorderTraversalBackTracking(TreeNode root){
    // 2. 确定终止条件
    if (root == null){
      return;
    }
    // 3. 后序遍历
    postorderTraversalBackTracking(root.left);
    postorderTraversalBackTracking(root.right);
    result.add(root.val);
  }

  public List<Integer> preorderTraversal(TreeNode root) {
    preorderTraversalBackTracking(root);
    return result;
  }

  // 1. 确定参数和返回值
  public void preorderTraversalBackTracking(TreeNode root){
    // 2. 确定终止条件
    if (root == null){
      return;
    }
    // 3. 前序遍历
    result.add(root.val);
    preorderTraversalBackTracking(root.left);
    preorderTraversalBackTracking(root.right);
  }

  public List<Integer> inorderTraversal(TreeNode root) {
    inorderTraversalBackTracking(root);
    return result;
  }
  // 1. 确定参数和返回值
  public void inorderTraversalBackTracking(TreeNode root){
    // 2. 确定终止条件
    if (root == null){
      return;
    }
    // 3. 中序遍历
    inorderTraversalBackTracking(root.left);
    result.add(root.val);
    inorderTraversalBackTracking(root.right);
  }
}
